1. Field of the Invention
The present invention relates to channel decoders for digital wireless communications devices. More particularly, the present invention provides a method and apparatus for a digital wireless communications device to decode in real-time a received signal which was encoded using a punctured convolutional code. In a preferred embodiment, a channel decoder is provided which permits Viterbi decoding of signals which have been encoded with a convolutional code, including a punctured convolutional code, without determining the branching metric in real-time.
2. Discussion of Related Art
FIG. 1 is a simplified block diagram of a reception portion of a digital wireless communications device 100, such as a digital cellular phone which may be used with a TMS320C5x digital signal processor made by Texas Instruments, Dallas Tex. or other suitable processor. A preferred digital cellular phone may include an antenna 102, a duplexer 104, a mixer 106, an oscillator 108, a demodulator 110, a 90xc2x0-phase shifter 112, an equalizer 114, a channel decoder 116, a speech decoder 118, a digital-to-analog converter (DAC) 120, and a speaker 122.
The reception portion of the digital cellular telephone of FIG. 1 may operate in the following manner. A digital communications signal may be received by the antenna 102 and passed through the duplexer 104 to the reception portion of the digital communications device 100. The mixer 106 steps the received signal to a lower workable frequency (called an intermediate frequency) by mixing the received signal with a frequency provided by an oscillator 108. The signal, now at an intermediate frequency, is demodulated by the demodulator 110. The demodulator 110 extracts information from the intermediate frequency. The demodulator may receive a signal from the oscillator 108 which has been shifted 90xc2x0 by the 90xc2x0-phase shifter 112. A preferred modulation (and thus demodulation) technique is differential quaternary phase-shift keying (DQPSK), but other modulation techniques may also be used.
The demodulated signal is then sent to the equalizer 114 to be equalized to account for channel distortion such as Rayleigh fading (caused by multi-path effects) and Doppler effects (caused by the movement of the transmitter with respect to the received signal). The equalizer 114 is essentially an inverse filter of channel distortion. The channel decoder 116 detects and corrects errors in the bit stream, demultiplexes control data, and feeds the data to the speech decoder 118. As discussed below, if a convolutional encoding scheme, such as a punctured convolutional encoding scheme, was used to encode the received signal, a Viterbi decoding scheme may be used to detect and correct errors in the bit stream. The channel decoded signal is then sent to the speech decoder 118, which decodes any speech encoding which may have been performed on the received signal. A preferred speech coding method is vector sum excited linear prediction (VSELP), but other speech coding methods may also be used. The DAC 120 converts the digital signal into an analog signal suitable to drive the speaker 122.
One method to improve the reliability of a telecommunications network is to add error control processing at the transmitting and receiving ends of the network. One method of doing this is to add redundancy to the transmitted signal so that the receiving channel decoder 116 may make a decoding decision based on more than a single bit.
One common type of error control technique used in digital telecommunications networks is a convolutional code. A convolutional code is a code which provides n output symbols for each group of k input symbols. The code rate is defined as R=k/n. For example, if two symbols are output for every one input symbol, the code rate is 1/2. While convolutional encoding provides adequate redundancy for effective error control, it also increases the bandwidth of the signal because it adds a number of symbols to the transmitted signal. The inverse of the code rate is known as the bandwidth expansion of the unpunctured convolutional encoder. Thus, for a 1/2 code rate, the bandwidth expansion is 2, i.e., the bandwidth used by signal is doubled.
One way to improve the bandwidth expansion of convolutional codes is to xe2x80x9cpuncturexe2x80x9d the code. Puncturing a convolutional code means that periodically a certain number of bits in the convolutional encoder output are deleted at a fixed rate. This rate is called the puncture rate.
FIG. 2 illustrates an example of a convolutional encoder 200. In this exemplary encoder 200, two bits Y1 and Y2 are provided to the convolutional encoder and the encoder outputs a bit Y0. The Y0 bit carries only forward error correction information and thus is referred to as a redundant bit. As seen in FIG. 2, a typical convolutional encoder is a 3-bit shift register having three states 202, 204, 206 interconnected by AND and XOR logic (not shown). The combined set of three bits 202, 204, 206 of encoder memory (S0, S1, S2) is typically referred to as the delay state. The output bits (Y0, Y1, Y2) are grouped into an output symbol typically referred to as the path state. Note that given a particular delay state (S0, S1, S2) not all path states may be possible in that time interval.
Because the encoder 200 may be considered to be a finite state machine, a finite state diagram may be used to represent the possible states the machine may be in at a particular time. FIG. 3 is a trellis diagram 300 of an encoder which may be in one of either of two states: 0 or 1. This trellis diagram 300 is often referred to as a Viterbi butterfly. As seen in FIG. 2, the encoder 200 has m delay elements (in this example, m=3) and may be described as having 2m (in this example, 8) states, a.k.a. trellis states. For each new information bit shifted into the register, r output bits (in this example, 3) are generated by the multiplexing of r different generator polynomials g, where g is a generator polynomial described by a set of XOR operations on selected delay elements of the encoder 200. For each steady state of the register, these output bits (or one output symbol) are used to describe the state transition from the previous steady state of the register to the current steady state of the register. This output symbol shall hereinafter be referred to as a xe2x80x9ctransition symbolxe2x80x9d. There are 2r (in this example, 8) possible different transition symbols.
For each current state, there are two possible new states. These states are determined by whether the new information bit is a 0 or 1. Likewise, for each current state there are two possible previous states (0 or 1). This is illustrated in FIG. 3, which is a trellis structure 300 illustrating the possible states of the convolutional encoder 200 of FIG. 2. In FIG. 3, the designation 0/xyz indicates a 0 input bit and a transition symbol of xyz; the designation 0/xyz indicates a 0 input bit and that the transition symbol is the complement of xzy (in the text, italicized type indicates xe2x80x9ccomplementxe2x80x9d.) The function of a decoder is to determine the most likely output. One way to do this is to use a sequence of states to determine the path having the lowest xe2x80x9ccostxe2x80x9d, i.e., the path which deviates the least from the received signal. Cost functions may be unique to each modulation technique. One commonly used cost function is a Hamming distance, which is often used for binary signals. (Although Hamming distances are described and claimed herein, a person skilled in the art readily recognizes that other suitable cost functions may be used.) A Viterbi decoder, for example, determines the most likely sequence of states experienced by the convolutional encoder 200 when it encodes the received signal.
A Hamming distance dh may be determined by accumulating the result of an exclusive-or (XOR) operation between each bit of the received code and the respective bits of the trellis branch. Given sufficient precision in the processor, a single XOR operation at symbol level may be used to determine the error symbol. This is followed by the accumulation of error bits, which requires additional operations. For example, if the result of the XOR on the three bit symbol is 110, it indicates that the first two bits of the received symbol are different from the reference transition symbol. Thus, the Hamming distance is the algebraic sum of the number of bits in error, in this case being two.
For each received symbol, the branch metrics for each of the possible states are calculated by comparing the received symbol with the two path metrics for each state. This is called the branch metric step. Then the path metrics are calculated by adding each branch metric with the surviving path metric from the state from which the branch originates. The two path metrics entering each state are then compared and the one having the lowest cost metric is chosen as the surviving path for that state. This is called the add/compare/select (ACS) step. This step is complicated when decoding a punctured convolutional code. The decoder decides which bits from the received symbols have been punctured (deleted) and to include in the dh accumulation only the result of the XOR operation for bits which have not been punctured. This results in additional computational complexity in the branch metric calculation stage.
After the surviving paths for all states and all received symbols are calculated, the received bitstream is determined by tracing back from the current state through each previous state to the first state. The state change for each transition is determined and consequently the input data to the convolutional codes causing that state change is also determined. This is called the trace back step.
The branch metric step is computationally intensive and is performed frequently even during a single transmission.
Therefore, it is an object of the present invention to provide an improved method and apparatus for performing the branch metric step without real-time computation.
This and other objects of the present invention are provided by an apparatus in a digital wireless communications device for efficiently determining the dh for trellis based decoders, such as decoders for punctured convolutional codes. In a preferred embodiment, dh is pre-determined for all codes and stored in program memory, thereby avoiding real-time computation of the metric.
Preferably, the inventive device comprises five components. These components include a state sequencing circuit, a Hamming distance table generator, a Hamming distance table, a Hamming distance retrieval circuit, and an ACS circuit.
The state sequencer groups all of the 2m possible states into groups of similar branch metrics. The Hamming distance table generator is responsive to the state sequencer and determines the Hamming distance for all combinations of puncture codes, received symbols, and transition symbols. This may be performed once and stored in permanent memory or may be performed each time the digital communications device is initialized and stored in a random access memory. The Hamming distance table is a memory arranged as a three dimensional table which stores the results of the Hamming distance table generator. The Hamming distance table receives addresses and data from the Hamming distance table generator. The table may be stored in a permanent memory or a volatile or random access memory. The Hamming distance retrieval circuit receives the puncture code and the received symbols and, based on these inputs, retrieves the appropriate information from the Hamming distance table. The ACS circuit is responsive to an output of the Hamming distance table and the state sequencer and calculates the surviving paths for the states in the order determined by the state sequencer.
As a result of the inventive device, the branch metric may be obtained without determining the branch metric in real-time. Rather, the branch metrics for all possible states and puncture codes are predetermined, stored in memory, and retrieved. This greatly reduces the computational needs of a trellis decoder, particularly for decoding a signal using a punctured convolutional code. As a result, the Viterbi decoding process may be performed more efficiently and with fewer computations.